Они же backreferences в регулярных выражениях.

Они очень близки, по сложности вычисления совпадения (разбора), к контекстно-зависимым грамматикам. Контекстно-зависимые грамматики позволяют порождать (и разбирать) программы с правильными простыми типами ( Read more... )

Первое, он простой. Второе, он определён контекстно-свободной грамматикой.

Идеальный кандидат на проверку идеи про приближение грамматик.

https://web.stanford.edu/~jurafsky/slp3/ - там много интересного про распознавание речи и начинается всё с нормализации и регулярных грамматик.

(glamour имеет в своих предках grammar и grimoir, которое означало волшебные заклинания когда-то очень давно; "регулярные волшебные ( Read more... )

Посмотрев на асимптотически интересные результаты работы регулярных выражений, решил вспомнить былое и собрать похожее на потоковых процессорах.

( Текст программы )

Можно ли задать регулярной грамматикой распознавание строки состоящей из четного количества единиц и нечетного нулей? Конечным автоматом без памяти - можно, говорят. И насколько задание этого распознавателя регулярной грамматикой будет сложнее по описанию, чем конечный автомат?( Мой вариант )